package Queue;

import java.util.*;

/**
 * @Classname JZ59队列的最大值
 * @Description TODO
 * @Date 2023/3/8 20:10
 * @Created by xjl
 */
public class JZ59队列的最大值 {
    /**
     * @description 单调队里的问题 要求的时间复杂度O(1)  可以使用栈 最大栈的结果
     * @param: null
     * @date: 2023/3/8 20:12
     * @return:
     * @author: xjl
     */
    class MaxQueue {

        Queue<Integer> q;
        Deque<Integer> d;

        public MaxQueue() {
            q = new LinkedList<Integer>();
            d = new LinkedList<Integer>();
        }

        public int max_value() {
            if (d.isEmpty()) {
                return -1;
            }
            return d.peekFirst();
        }

        public void push_back(int value) {
            while (!d.isEmpty() && d.peekLast() < value) {
                d.pollLast();
            }
            d.offerLast(value);
            q.offer(value);
        }

        public int pop_front() {
            if (q.isEmpty()) {
                return -1;
            }
            int ans = q.poll();
            if (ans == d.peekFirst()) {
                d.pollFirst();
            }
            return ans;
        }
    }
}
